/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-15 22:06:30
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-15 22:06:38
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法46.最小的k个数(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
 */
class Solution {
public:
    // vector<int> inventoryManagement(vector<int>& stock, int cnt) {
    //     /****** 排序后取前k个小的元素,时间复杂度O(n*logN)******/
    //     sort(stock.begin(),stock.end());
    //     vector<int> ret(cnt, 0);
    //     for(int i = 0; i < cnt; i++) ret[i] = stock[i];
    //     return ret;
    // }
    vector<int> inventoryManagement(vector<int>& nums, int k) {
        /***** 基于快排的快速选择算法,时间复杂度O(n) ******/
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1,  k); // 将数组中前k小的元素丢到前面
        return {nums.begin(), nums.begin() + k};
    }
    void qsort(vector<int>& nums, int l, int r, int k) {
        if(l >= r) return;
        int key = getRandom(nums, l, r); // 获取随机基准值
        int left = l - 1, right = r + 1, i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }
        // 分情况讨论三个区间 [l,left] [left+1,right-1] [right,r]
        int a = left - l + 1, b = right -1 - (left+1) + 1; // a,b为区间的元素个数
        if(a >= k) return qsort(nums, l, left, k);
        else if(a + b >= k) return;
        else return qsort(nums, right, r, k - a - b);
    }
    int getRandom(vector<int>& nums, int l, int r) {
        return nums[l + rand() % (r - l + 1)];
    } 
};